#include "abb.h"
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <math.h>

typedef struct Branch *Tree;
struct sAbb {
  int* cant;
  Tree t;
};

struct Branch {
  Key k; 
  Data d;
  Tree l, r;
};

#define Leaf ((Tree) NULL)

Tree
tree_add(Tree t ,Key k ,Data d , int* cant);

Tree
mktree(Tree l , Key k , Data d , Tree r);

Tree
tree_del (Tree t, Key k,  int* cant);

void
tree_toCinta (Tree t ,cw c_disco);

Tree
tree_destroy(Tree t);

Tuple
max (Tree t);

Tree
del_max (Tree t);

Tuple
min (Tree t);

Tree
del_min (Tree t);

void
tree_pprint (Tree t, FILE *);

int altura(Tree t);

int nbal(Tree t);

Tree ball(Tree t);

Tree balr(Tree t);

Tree rotr(Tree t);

Tree rotl(Tree t);

Tree calcalt(Tree t);

Bool isAVL(Tree t);


Abb
abb_empty (void){
	Abb h= NULL;
	h = (Abb) calloc (1,sizeof (struct sAbb));
	if (h==NULL)
		warn(ERRFMT,"abb_empty : Lack of Free Memory!",__LINE__);
	else {
		h ->t =Leaf;
		h->cant = (int*) calloc (1,sizeof (int));
		if (h->cant==NULL){
			warn(ERRFMT,"abb_empty : Lack of Free Memory!",__LINE__);
			free(h);
			h =NULL;
			}else{
			*h->cant = 0;
		}
	}
	return h;
}

void
abb_add (Abb h, Key k, Data d)
{
	h->t = tree_add(h->t,k,d,h->cant);
}

Tree
tree_add(Tree t ,Key k ,Data d , int* cant){
	if( t==Leaf )
	{
		*cant = *cant + 1;
		return mktree( Leaf , k ,d , Leaf );
	}
	else
	{ 
		if (!key_eq(k,t->k))
		{
			if(key_le(t->k,k))
			{
				t->r = tree_add (t->r,k,d,cant);
				return balr(t);/*Estaríamos en el caso 5: right - ?*/
			}
			else
			{
				t->l = tree_add (t->l,k,d,cant);
				return ball(t);/*Estaríamos en el caso 4: left - ?*/
			}
		}
	}
	return t;
}

/*
{Pre: l=L ^ k=K ^ d=D ^ r=R ^ t = NULL }
	t = mktree (l , k , d , r )
{Pos: l=L ^ k=K ^ d=D ^ r=R ^ t = <{l,k,d,r}>}
*/
Tree
mktree(Tree l , Key k , Data d , Tree r){
	Tree ret =Leaf;
	ret = (Tree) calloc (1,sizeof (struct Branch));
	if (ret ==NULL){
		warn(ERRFMT,"A voice from Far Beyond: Lack of Free Memory!",__LINE__);
	}else{
		
		ret->l = l;
		ret->k = key_clone (k);
		ret->d = data_clone (d);
		ret->r = r;
	}
	return ret;
}	

Bool
abb_exists (Abb h, Key k){
	Bool b = FALSE;
	Tree aux = h->t;
	/* {INV: b = (aux.[] = (k,d)) } */
	while(aux!=Leaf && !b){
		b = key_eq(k,aux->k);
		if (!b){
			if(key_le(aux->k,k))
				aux = aux->r;
			else
				aux = aux->l;
		}
	}
	return	b;
}

Data
abb_search (Abb h, Key k){
	Data d =NULL;
	Tree aux = Leaf;
	assert (h!=NULL && k!=NULL);
	aux = h->t;
	/*{Inv: d=NULL (v) d = (aux.[]->d)}*/ 
	while(aux!=Leaf && d==0x0)
	{
		if (!key_eq(k,aux->k)){
			if(key_le(aux->k,k)){
				aux = aux->r;
			}else{
				aux = aux->l;
			}
		}else{
			d = data_clone(aux->d);
		}
	}
	return	d;
}

int
abb_length (Abb h){
	assert (h!=NULL);
 	return *h->cant;
}

void
abb_del (Abb h, Key k){
	assert (h!=NULL && k!=NULL);
	if (*h->cant<2)
	{
		h->t = tree_destroy(h->t);
		*h->cant = 0;
	}
	else
		h->t = tree_del(h->t,k,h->cant);
}

Tree
tree_del (Tree t, Key k, int* cant){
	Tuple tu=NULL;
	int i=-1,j=-1;
	Tree aux1=t;
	Tree padre=t;
	Tree abuelo=t;
	if (t!=Leaf){
		while(aux1!=Leaf && !key_eq(k,aux1->k))
		{
			if(key_le(aux1->k,k)){
				i = 1;
				abuelo = padre;
				padre = aux1;
				aux1 = aux1->r;
				if (key_le(padre->k,abuelo->k))
					j=0;
				else if (key_le(abuelo->k,padre->k))
					j=1;
			}else{
				i = 0;
				abuelo = padre;
				padre = aux1;
				aux1 = aux1->l;
				if (key_le(padre->k,abuelo->k))
					j=0;
				else if (key_le(abuelo->k,padre->k))
					j=1;
			}
		}
		if (aux1!=Leaf)
		{
			aux1->k = key_destroy (aux1->k);
			aux1->d = data_destroy (aux1->d);
			if (aux1->l!=Leaf && nbal(aux1)>=0)
			{
				tu = max(aux1->l);
				aux1->k = tuple_fst(tu);
				aux1->d = tuple_snd(tu);
				aux1->l = del_max(aux1->l);
			}
			else if (aux1->r!=Leaf && nbal(aux1)<0)
			{
				tu = min(aux1->r);
				aux1->k = tuple_fst(tu);
				aux1->d = tuple_snd(tu);
				aux1->r = del_min(aux1->r);
			}
			else	/* este caso es: aux1->l = aux1->r = NULL */
			{
				if (i==1)
				{
					padre->r = Leaf;
					if (key_eq(t->k,padre->k))
						t = ball(padre);
					else
						padre = ball(padre);
				}
				else if (i==0)
				{
					padre->l = Leaf;
					if (key_eq(t->k,padre->k))
						t = balr(padre);
					else
						padre = balr(padre);
				}
				if (j==0)
					abuelo->l = padre;
				else if (j==1)
					abuelo->r = padre;
				aux1 = tree_destroy(aux1);
			}
			*cant = *cant - 1;
			tu = tuple_destroy(tu);
		}
	}
	return t;
}

Tuple
max (Tree t){
	Tree aux = Leaf;	
	assert(t!=Leaf);
	aux = t;
	while (aux->r != Leaf)
		aux = aux->r;
	return tuple_fromKeyData(aux->k,aux->d);
}

Tuple
min (Tree t){
	Tree aux = Leaf;
	assert(t!=Leaf);
	aux = t;
	while (aux->l != Leaf)
		aux = aux->l;
	return tuple_fromKeyData(aux->k,aux->d);
}

Tree
del_max (Tree t)
{
	Tree aux1=Leaf;
	Tree aux2=Leaf;
	assert (t!=Leaf);
	aux1 = t;

	if (aux1->r==Leaf)
	{
		t = aux1->l;
		aux1->l = Leaf;
		aux1 = tree_destroy(aux1);
	}
	else
	{
		while (aux1->r != Leaf) {
			aux2 = aux1;
			aux1 = aux1->r;
		}
		aux2->r = aux1->l;
		aux1->l = Leaf;
		aux1 = tree_destroy(aux1);
	}
	return t;
}

Tree
del_min (Tree t)
{
	Tree aux1=Leaf;
	Tree aux2=Leaf;
	assert (t!=Leaf);
	aux1 = t;

	if (aux1->l==Leaf)
	{
		t = aux1->r;
		aux1->r = Leaf;
		aux1 = tree_destroy(aux1);
	}
	else
	{
		while (aux1->l != Leaf) {
			aux2 = aux1;
			aux1 = aux1->l;
		}
		aux2->l = aux1->r;
		aux1->r = Leaf;
		aux1 = tree_destroy(aux1);
	}
	return t;
}

Tree
tree_destroy(Tree t){
	if(t!=Leaf){
		t->k = key_destroy(t->k);
		t->d = data_destroy(t->d);
		t->l = tree_destroy(t->l);
		t->r = tree_destroy(t->r);
		free(t);
		t =NULL;
	}
	return t;
}

Abb
abb_destroy(Abb h){
	h->t = tree_destroy (h->t);
	free(h->cant); 
	h->cant = NULL;
	free (h);
	h = NULL;
	return h;
}

void
abb_pprint (Abb h)
{
	FILE *fout = fopen("graph.dot", "w");
	fprintf(fout, "digraph abb {\n");
	if(h!=NULL)
		tree_pprint(h->t, fout);
	fprintf(fout, "}\n");
	fclose(fout);
}

void
tree_pprint (Tree t, FILE * fout)
{
	char k[KEY_MAX_LENGTH], k2[KEY_MAX_LENGTH];
	char* d;
	if(t!=Leaf)
	{
/*		printf("*******\n");
		printf("IZQ :\n");*/
		tree_pprint(t->l, fout);
		key_toString(t->k,k);
		d = data_toString(t->d);
		printf("(%s , %s)\n",k,d);
		if( t->l != Leaf ){
			key_toString(t->l->k,k2);
			fprintf(fout, "\t%s -> %s;\n", k, k2);
		}
		if( t->r != Leaf ){
			key_toString(t->r->k,k2);
			fprintf(fout, "\t%s -> %s;\n", k, k2);
		}
		free(d);
/*		printf("DER :\n");*/
		tree_pprint(t->r, fout);
/*		printf("*******\n");
	}
	else
	{
		printf("-------\n");
		printf("NADA\n");
		printf("-------\n");*/
	}
}
Abb
abb_fromFile(char *nomfile)
{
	Key k = NULL;
	Data d = NULL;
	Abb h = abb_empty();
	cr c_disco = cr_create(nomfile);
	if (c_disco == NULL)
    	{
		warn(ERRFMT,"abb_fromFile: no such file",__LINE__);
	}
	else
	{
		cr_arr(c_disco);

		while(!cr_fin(c_disco))
		{
			k = tuple_fst( cr_elec(c_disco));
			d = tuple_snd( cr_elec(c_disco));
			abb_add (h ,k,d);
			k = key_destroy (k);
			d = data_destroy (d);
			cr_av(c_disco);
		}
	c_disco = cr_destroy(c_disco);
	}
	return h;
}

void
abb_toFile (char *nomfile, Abb h)
{
	cw c_disco = cw_create(nomfile);
	if (h->cant==NULL){
		warn(ERRFMT,"abb_toFile: Nothing to save",__LINE__);
	}else{
		cw_arr(c_disco);
		tree_toCinta (h->t , c_disco );
		c_disco = cw_destroy(c_disco);
	}
	
}

void
tree_toCinta (Tree t ,cw c_disco)
{
       Tuple tu=NULL;
       if(t != Leaf)
       {
               tree_toCinta(t->l, c_disco);
               tu = tuple_fromKeyData (t->k , t->d);
               cw_ins(c_disco,tu);
               tu = tuple_destroy(tu);
               tree_toCinta(t->r, c_disco);
       }
}

int altura(Tree t)
{
	int altL,altR;
	if(t == Leaf) 
		return -1;
	else
	{
		altL=altura(t -> l);
		altR=altura(t -> r);
		if(altL >= altR)
			return 1 + altL;
		else
			return 1 + altR;
	}
}

Bool invariante(Abb h)
{
	return isAVL(h -> t);	
}

Bool isAVL(Tree t)
{
	return (t == Leaf) || (fabs(altura(t -> l) - altura(t -> r)) <= 1 && isAVL(t -> l) && isAVL(t -> r));
}

int nbal(Tree t)
{
	if(t == Leaf)
		return 0;
	else
		return altura(t -> l) - altura(t -> r);
}

Tree ball(Tree t)
{
	/*Los siguientes assert saltarían cuando nuestra hipótesis (que estamos insertando sobre un árbol que estaba balanceado) es falsa...los dejo por ahora*/
	assert(t != Leaf);
	assert(-1 <= nbal(t) && nbal(t) <= 2);
	
	if(nbal(t) == 2)
	{
		assert(fabs(nbal(t -> l) <= 1));
		if(nbal(t -> l) == 1)
			return rotr(t);
		else
		{
			t -> l = rotl(t -> l);
			return rotr(t);
		}
	}
	else
		return t;/*Por que entonces el árbol esta balanceado */
}

Tree rotr(Tree t)
{
	Tree aux;
	assert(t -> l != Leaf);
	aux = t -> l -> r;
	t -> l -> r = t;
	t = t -> l;
	t -> r -> l = aux;
	
	return t;
}

Tree rotl(Tree t)
{
	Tree aux;
	assert(t -> r != Leaf);
	aux = t -> r -> l;
	t -> r -> l = t;
	t = t -> r;
	t -> l -> r = aux;
	return t;
}

Tree balr(Tree t)
{
	/*Los siguientes assert saltaran cuando nuestra hipotesis (que estamos insertando sobre un arbol que estaba balanceado) es falsa...los dejo por ahora*/
	assert(t != Leaf);
	assert(-2 <= nbal(t) && nbal(t) <= 1);
	
	if(nbal(t) == -2)
	{
		assert(fabs(nbal(t -> r) <= 1));
		if(nbal(t -> r) == 1)
		{/*Este sera el caso right-left. Con rotl lo llevamos al caso left-right y dejamos que ball se encargue de solucionarlo*/
			t = ball(rotl(t));
			return t;
		}
		else
		{
			t = rotl(t);	/*Este sera el caso right-right. Basta con rotar a la izquierda*/
			return t;
		}
	}
	else
		return t;/*Por que entonces el arbol esta balanceado */
}
